import random

def compute_answer(n, opL, aVal, opR, bVal):
    """
    根据动态规划系数倒推法计算最大总人数.
    初始状态：左右各1人，F(n, L, R) = L + R, 即 A = 1, B = 1, C = 0.
    """
    A, B, C = 1, 1, 0
    for i in range(n - 1, -1, -1):
        a = aVal[i]
        b = bVal[i]
        if A > B:
            # 情况1：A > B，将本门额外人数全部分给左侧
            if opL[i] == "x":
                newA = A * a
            else:
                newA = A

            if opR[i] == "x":
                newB = B + A * (b - 1)
            else:
                newB = B

            newC = C
            if opL[i] == "+":
                newC += A * a
            if opR[i] == "+":
                newC += A * b
        elif A < B:
            # 情况2：A < B，将新增人数全部分给右侧
            if opL[i] == "x":
                newA = A + B * (a - 1)
            else:
                newA = A

            if opR[i] == "x":
                newB = B * b
            else:
                newB = B

            newC = C
            if opL[i] == "+":
                newC += B * a
            if opR[i] == "+":
                newC += B * b
        else:
            # 情况3：A == B，两侧无差别，分配方式无所谓
            if opL[i] == "x":
                newA = A * a
            else:
                newA = A

            if opR[i] == "x":
                newB = A * b  # 因为 A == B
            else:
                newB = A

            newC = C
            if opL[i] == "+":
                newC += A * a
            if opR[i] == "+":
                newC += A * b

        A, B, C = newA, newB, newC
    return A + B + C

def generate_gates(n):
    """
    随机生成 n 对门，每扇门包含两个操作：
      - 操作符为 "+" 或 "x"
      - 数字为 1 到 9
    返回：opL, aVal, opR, bVal 四个列表
    """
    ops = ["+", "x"]
    opL, opR, aVal, bVal = [], [], [], []
    for i in range(n):
        opL.append(random.choice(ops))
        aVal.append(random.randint(1, 9))
        opR.append(random.choice(ops))
        bVal.append(random.randint(1, 9))
    return opL, aVal, opR, bVal

def print_gates(opL, aVal, opR, bVal):
    """
    按顺序打印出每扇门的操作.
    """
    n = len(opL)
    for i in range(n):
        print(f"门 {i+1}: {opL[i]} {aVal[i]}    {opR[i]} {bVal[i]}")

def main():
    print("欢迎来到最大总人数游戏!")
    print("规则说明：")
    print("在这个游戏中，一个关卡由 n 对门组成。每对门包含一个左门和一个右门。每个门执行两种操作中的一种：")
    print("加法运算(+ a)：将车道上的人数增加一个常数。乘法运算(x a)：将车道上的当前人数乘以一个整数 a 。这意味着该车道的人数增加了 (a−1) 倍。")
    print("每次操作增加的人数可以分配到任一车道。但是，已在一条车道上的人数不能被移动到另一条车道上。")
    print("最初，每个车道上都有一个人")
    print("你的任务是根据最优决策，计算最终能达到的最大总人数。")
    
    left_bound = 1
    right_bound = 11

    # 循环直到区间收敛（例如 left_bound + 1 >= right_bound）
    while left_bound + 1 < right_bound:
        mid = (left_bound + right_bound) // 2
        print(f"\n当前门数（难度）: {mid}")
        opL, aVal, opR, bVal = generate_gates(mid)
        print("随机生成的门如下：")
        print_gates(opL, aVal, opR, bVal)
        
        # 计算正确答案
        correct_answer = compute_answer(mid, opL, aVal, opR, bVal)
        # 提示用户输入答案
        user_input = input("请计算使用最优决策后的最大总人数并输入你的答案: ")
        try:
            user_answer = int(user_input.strip())
        except:
            print("输入格式错误，请输入一个整数。")
            continue

        if user_answer == correct_answer:
            print("回答正确！难度提升～")
            left_bound = mid  # 回答正确，左边界更新（提高难度）
        else:
            print(f"回答错误！正确答案是 {correct_answer}。")
            right_bound = mid  # 回答错误，右边界更新（降低难度）
        
        # print(f"当前难度区间：{left_bound} 到 {right_bound}")

    print("\n游戏结束！")
    print(f"最终确定你的IQ为: {left_bound+6}0")

if __name__ == "__main__":
    main()
